package com.linwen.excise.leetcode;

import java.util.Arrays;

/**
 * @ClassName _88合并两个有序数组
 * @Description TODO
 * @Author zero
 * @DATE 2024/4/25 11:29 PM
 * @Version 1.0
 */
public class _88合并两个有序数组 {
    public static void main(String[] args) {
        int[] num1 = new int[]{1,2,3,0,0,0};
        int[] num2 = new int[]{2, 5, 6};
        int m = 3;
        int n = 3;
        merge2(num1, m, num2, n);
        for (int i = 0; i < num1.length; i++) {
            System.out.println(num1[i]);
        }
    }

    // 后指针
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 || j >= 0) {
            if(i < 0){
                nums1[k] = nums2[j--];
            }else if(j<0){
                nums1[k] = nums1[i--];
            }else if(nums1[i] > nums2[j]){
                nums1[k] = nums1[i--];
            }else {
                nums1[k] = nums2[j--];
            }
            k--;
        }
    }

    // 赖皮
    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i <n ; i++) {
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

    // 插入排序方法
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
            int j = m + i;
            while (j>0) {
                if (nums1[j] < nums1[j - 1]) {
                    int temp = nums1[j];
                    nums1[j] = nums1[j - 1];
                    nums1[j - 1] = temp;
                    j--;
                } else {
                    break;
                }
            }
        }

    }
}
